public class Solution {
    public static void main(String[] args) {
        int[] preorder = {3,9,20,15,7};
        int[] inorder = {9,3,15,20,7};
        int[] postorder = {9,15,7,20,3};
        Solution solution = new Solution();

        TreeNode root = solution.buildTree(inorder,postorder);
        System.out.println(root.val);
    }

    // 内部类定义节点
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) {
            this.val = val;
        }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    // 根据前序、中序创建二叉树
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder,inorder,0,inorder.length-1);
    }
    // 递归前序创建二叉树
    int preindex = 0;  // 重点1：定义全局变量，取消递归的干扰，从而保证从前到后依次遍历preorder数组
    private TreeNode buildTreeChild(int[] preorder,int[] inorder,int begindex,int Endindex){
        // 重点2：递归结束条件，也防止数组越界
        if(begindex > Endindex){
            return null;
        }

        TreeNode root = new TreeNode(preorder[preindex]);
        // 求前序遍历的节点在中序遍历中作为根节点的位置
        int rootindex_inorder = findIndex(preorder,inorder);
        // 重点三：查完前序的节点在中序中根节点位置，再把遍历前序的下标preindex+1
        preindex++;


        root.left = buildTreeChild(preorder,inorder,begindex,rootindex_inorder-1);
        root.right = buildTreeChild(preorder,inorder,rootindex_inorder+1,Endindex);
        return root;
    }
    // 求前序的节点在中序遍历的位置
    private int findIndex(int[] preorder,int[] inorder){
        int i = 0;
        while(i<inorder.length){
            if(preorder[preindex] == inorder[i]){
                return i;
            }
            i++;
        }
        return -1;
    }


    // 中序和后序遍历序列创建二叉树
    int postIndex = 0;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postIndex = postorder.length-1;
        return buildTreeChild(inorder,postorder,0,inorder.length-1);
    }
    private TreeNode buildTreeChild(int[] inorder, int[] postorder, int begindex, int endindex){
        if(begindex>endindex){
            return null;
        }

        TreeNode root = new TreeNode(postorder[postIndex]);
        int rootindex_inorder = findIndex(inorder,postorder);
        postIndex--;

        root.right = buildTreeChild(inorder,postorder,rootindex_inorder+1,endindex);
        root.left = buildTreeChild(inorder,postorder,begindex,rootindex_inorder-1);
        return root;
    }
    private int findIndex(int[] inorder, int[] postorder){
        int i = 0;
        while(i<inorder.length){
            if(inorder[i] == postorder[postIndex]){
                return i;
            }
            i++;
        }
        return -1;
    }
}